package dp;

/**
 * leet-code(647) 回文子串
 *
 * @author Ringo
 * @date 2021/9/6 21:35
 */
public class CountSubstrings {

    public static void main(String[] args) {
        String s = "abaa";
        System.out.println(countSubstrings1(s));
    }

    // 中心扩展 ==========================================================================================================
    public static int countSubstrings1(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; ++i) {           // 中心点
            for (int j = 0; j <= 1; ++j) {      // j=0表示奇数回文; j=1表示偶数回文
                int left = i, right = i + j;
                while (left >= 0 && left < n && right >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                    ++count;
                    --left;
                    ++right;
                }
            }
        }
        return count;
    }

    // 递归 ==========================================================================================================
    // 找出回文子串的个数
    public static int countSubstrings(String s) {
        if (s == null || s.length() == 0)
            return 0;

        int count = 0;
        int n = s.length();

        for (int L = 1; L <= n; ++L) {
            for (int start = 0; start < n; ++start) {
                // L = end - start + 1
                int end = start + L - 1;
                if (end >= n) continue;
                if (dfs(s, start, end)) ++count;
            }
        }
        return count;
    }

    /**
     * 判断字符串 s 从 start ~ end 是否是回文
     *
     * @param start 包括
     * @param end   包括
     */
    private static boolean dfs(String s, int start, int end) {
        if (s.charAt(start) != s.charAt(end))
            return false;
        if (start >= end)
            return true;
        return dfs(s, start + 1, end - 1);
    }
}
